/*
题目：有序链表转换成二叉搜索树
给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
 */
public class SortedListToBST {
    //不破坏链表结构
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head, null);
    }

    //end 定义为不能到达的节点
    private TreeNode buildTree(ListNode start, ListNode end) {
        if (start == end) {
            return null;
        }
        if (start.next == null) {
            return new TreeNode(start.val);
        }
        ListNode mid = searchMidNode(start, end); //寻找中间节点
        TreeNode root = new TreeNode(mid.val);

        root.left = buildTree(start, mid);
        root.right = buildTree(mid.next, end);
        return root;
    }

    private ListNode searchMidNode(ListNode head, ListNode end) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != end && fast.next != end) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }


    //断开了链表
    public TreeNode sortedListToBSTOpen(ListNode head) {
        return buildTree(head);
    }

    private TreeNode buildTree(ListNode start) {
        if (start == null) {
            return null;
        }
        if (start.next == null) {
            return new TreeNode(start.val);
        }
        ListNode mid = searchMidNode(start); //寻找中间节点
        ListNode nextNode = mid.next;
        mid.next = null; //断开

        TreeNode root = new TreeNode(nextNode.val);
        root.left = buildTree(start);
        root.right = buildTree(nextNode.next);
        return root;
    }

    //寻找中间节点
    private ListNode searchMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null; //记录slow的上一个节点
        while (fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        return prev;
    }
}
